package problem0023

func mergeKLists2(lists []*ListNode) *ListNode {
	if len(lists) == 0 {
		return nil
	}
	if len(lists) == 1 {
		return lists[0]
	}

	var res *ListNode = lists[0]
	for ii := 1; ii < len(lists); ii++ {
		res = doMerge(res, lists[ii])
	}
	return res
}

func doMerge(a, b *ListNode) (res *ListNode) {

	if a == nil {
		return b
	}
	if b == nil {
		return a
	}

	var head *ListNode

	if a.Val > b.Val {
		head = b
		b = b.Next
	} else {
		head = a
		a = a.Next
	}

	tmp := head
	for a != nil && b != nil {
		// fmt.Println("start")
		// fmt.Println("a", gconv.Export(l2s(a)))
		// fmt.Println("b", gconv.Export(l2s(b)))
		// fmt.Println("tmp", gconv.Export(l2s(tmp)))
		if a.Val > b.Val {
			tmp.Next = b
			b = b.Next
		} else {
			tmp.Next = a
			a = a.Next
		}

		tmp = tmp.Next
		// fmt.Println("===>")
	}
	// fmt.Println("out")

	if a == nil {
		tmp.Next = b
	}
	if b == nil {
		tmp.Next = a
	}
	// fmt.Println("end")
	return head
}
